/**
 * 借用 3-2 的程序框架，测试非递归遍历方法
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// #include "../base/Tree-Traversal-Level.c"
// #include "../base/Tree-Traversal-Recursive.c"
#include "../base/Tree-Traversal-NonRecursive.c"


/* current ===============================*/
void visitTreeNode(TreeNode* node) {
    printf("%d ", node->data);
}

Tree read(TreeNode* nodes) {
    int n;
    scanf("%d", &n);
    // 是否叶子节点
    int *isLeave = (int*) malloc(sizeof(int)*n);
    memset(isLeave, 0, sizeof(int)*n);
    for (int i=0; i<n; i++) {
        char slidx[5], sridx[5];
        scanf("%s %s", slidx, sridx);
        char lidx = slidx[0];
        char ridx = sridx[0];
        nodes[i].data = i;
        // printf("%d) %d %s %s\n", i, nodes[i].data, lidx, ridx);
        if (lidx == '-') {
            nodes[i].left = NULL;
        } else {
            nodes[i].left = &nodes[lidx-'0'];
            isLeave[lidx-'0'] = 1;
        }
        if (ridx == '-') {
            nodes[i].right = NULL;
        } else {
            nodes[i].right = &nodes[ridx-'0'];
            isLeave[ridx-'0'] = 1;
        }
    }
    Tree root = NULL;
    for (int i=0 ;i<n; i++) {
        if (!isLeave[i]) {
            root = &nodes[i];
            break;
        }
    }
    free(isLeave);
    return root;
}

#define MAX_SIZE 10
int main() {
    // 预先分配t1, t2的内存空间
    TreeNode t1nodes[MAX_SIZE];
    Tree tree = read(t1nodes);
    
    printf("前序: ");
    preorderTraversal(tree);
    printf("\n");
    printf("中序: ");
    inorderTraversal(tree);
    printf("\n");
    printf("后序: ");
    postorderTraversal(tree);
    printf("\n");
    
    return 0;
}

// 前序: 3 2 0 1 7 4 6 5
// 中序: 1 0 2 3 4 7 5 6
// 后序: 1 0 2 4 5 6 7 3